package com.lenl.arithmetic.tenusablealgorithm.dynamic;

import java.util.Arrays;

/**
 * @author Lenl
 * @version v1.0
 * @create 2022-05-14 12:33
 * @description 动态规划 背包问题
 */
public class KnapsackProblem {
    public static void main(String[] args) {
        //物品重量
        int[] w={1,4,3};//物品重量
        int[] val={1500,3000,2000};//物品价值
        int m=4;//背包容量
        int n=val.length;//物品个数
        //为记录商品放入的情况，定义二维数组
        int[][] path=new int[n+1][m+1];
        int maxI=0;
        int maxJ=0;

        //创建二维数组
        //v[i][j] 表示前i个物品中能装入重量为j的最大价值
        int[][] v=new int[n+1][m+1];
        //初始化第一行第一列
        for (int i=0;i<v.length;i++){
            v[i][0]=0;
        }
        for (int i=0;i<v[0].length;i++){
            v[0][i]=0;
        }

        //根据公式动态规划处理
        for (int i=1;i<v.length;i++){
            for (int j=1;j<v[0].length;j++){
                //不处理第一行第一列
                //公式
                if(w[i-1]>j){
                    v[i][j]=v[i-1][j];
                }else{
                    //公式调整
                    //v[i][j]=Math.max(v[i-1][j],val[i-1]+v[i-1][j-w[i-1]]);
                    //为记录商品，需要拆解
                    if(v[i-1][j]<val[i-1]+v[i-1][j-w[i-1]]){
                        v[i][j]=val[i-1]+v[i-1][j-w[i-1]];
                        path[i][j]=1;
                        maxI=i;
                        maxJ=j;
                    }else{
                        v[i][j]=v[i-1][j];
                    }
                }
            }
        }


        //输出v
        for (int i=0;i<v.length;i++){
            System.out.println(Arrays.toString(v[i]));
        }
        //输出path
        for (int i=0;i<path.length;i++){
            System.out.println(Arrays.toString(path[i]));
        }
        //输出最佳结果
        System.out.println("最大值为"+v[maxI][maxJ]);
        //输出放入了哪些商品
        int i=path.length-1;
        int j=path[0].length-1;
        while (i>0&&j>0){
            if(path[i][j]==1){
                System.out.println("背包放入了第"+i+"个商品");
                j-=w[i-1];
            }
            i--;
        }


    }
}
